package edu.princeton.cs.algs4;

import edu.princeton.cs.stdlib.In;
import edu.princeton.cs.stdlib.StdOut;

/*************************************************************************
 * Compilation: javac DepthFirstSearch.java Execution: java DepthFirstSearch
 * filename s Dependencies: Graph.java
 * 
 * Run depth first search on an undirected graph. Runs in O(E + V) time.
 * 
 * % java DepthFirstSearch tinyG.txt 0 0 1 2 3 4 5 6 not connected
 * 
 * % java DepthFirstSearch tinyG.txt 9 9 10 11 12 not connected
 * 
 *************************************************************************/

public class DepthFirstSearch {
	private boolean[] marked; // marked[v] = is there an s-v path?
	private int count; // number of vertices connected to s

	public DepthFirstSearch(Graph G, int s) {
		marked = new boolean[G.V()];
		dfs(G, s);
	}

	// depth first search from v
	private void dfs(Graph G, int v) {
		marked[v] = true;
		for (int w : G.adj(v)) {
			if (!marked[w]) {
				dfs(G, w);
			}
		}
	}

	// is there an s-v path?
	public boolean marked(int v) {
		return marked[v];
	}

	// number of vertices connected to s
	public int count() {
		return count;
	}

	// test client
	public static void main(String[] args) {
		In in = new In(args[0]);
		Graph G = new Graph(in);
		int s = Integer.parseInt(args[1]);
		DepthFirstSearch search = new DepthFirstSearch(G, s);
		for (int v = 0; v < G.V(); v++) {
			if (search.marked(v))
				StdOut.print(v + " ");
		}

		StdOut.println();
		if (search.count() != G.V())
			StdOut.println("not connected");
		else
			StdOut.println("connected");
	}

}
